package com.woniuxy.test_map.my_hashmap;

/**
 * description: SxHashMap <br>
 * date: 2022/2/4 12:21 上午 <br>
 * author: shesaifei <br>
 * version: 1.0 <br>
 */

/**
 * 自定义HashMap
 */
public class SxHashMap {
    //核心数组(位桶数组 bucket array)
    Node[] table;
    int size; //存放键值对的个数

    public SxHashMap() {
        table = new Node[16]; //一般定义成2的整数幂
    }

    public void put(Object key, Object value) {
        //定义了新的节点对象
        Node newNode = new Node();
        newNode.hash = myHash(key.hashCode(), table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;

        Node temp = table[newNode.hash];

        Node iterLast = null;
        boolean keyRepeat = false;
        if (temp == null) {
            //此处数组元素为空，则直接将新节点放进去
            table[newNode.hash] = newNode;
            size++;
        } else {
            //此处数组不为空。则遍历对应的链表
            while (temp != null) {
                //判断key如果重复，则覆盖
                if (temp.key.equals(key)) {
                    keyRepeat = true;
                    //只覆盖value即可。其他的值(hash,key,next)保持不变
                    temp.value = value;
                    break;
                } else {
                    //key不重复，则遍历下一个
                    iterLast = temp;
                    temp = temp.next;
                }
            }
            if (!keyRepeat) {
                //没有发生key重复的情况，则添加到链表的最后
                iterLast.next = newNode;
                size++;
            }
        }
    }

    public static void main(String[] args) {
        SxHashMap m = new SxHashMap();
        m.put(10, "aa");
        m.put(20, "bb");
        m.put(30, "cc");
        m.put(20, "ss");
        m.put(21, "gg");
        m.put(37, "hh");
        m.put(53, "xx");
        m.put(69, "zz");
        m.put(85, "pp");
        System.out.println(m);
//        for (int i = 0; i <100 ; i++) {
//            //相同的哈希值 5 21 37 53 69 85
//            System.out.println(i+"--"+ m.myHash(i,16));
//        }

    }

    public int myHash(int v, int length) {
        //直接位运算，效率高
        //System.out.println("hash in myHash:"+(v&(length-1)));
        //取模运算，效率低
        //System.out.println("hash in myHash:"+(v%(length-1)));
        return v & (length - 1);
    }
}
